# Full text of "A pathfinding algorithm for a myopic robot"

## See other formats

^^^^^^^^^1 A U T I C S A Pathfinding Algorithm for a 2 &JSa»J3 2££ ^£ (PAGES) S (NASA CR OR TMX OR AD NUMBER) IMBER) J ET V> M L i 11 GPO PRICE $ CSFTI PRICE(S) $ Hard copy (HC) Microfiche (MF) ff653 July 65 3*&*D c 63' (THRU) (CODE) £1 (CATEGORY) * 1 1 fj § 1 1 1 a ■ lilllll 1 1 1 1 ft 1 ■lllil liSiii spin • til llilBiilllr V W NATIONAL AERONAUTICS AND SPACE ADMINISTRATION Technical Report 32-1288 A Path finding Algorithm for a Myopic Robot Larry Y. Urn Approved by &S5* W. F. Scott, Manager Flight Computers and Sequencers Section J i T PRO P U L S I O N LABORATO R Y CALIFORNIA INSTITUTE OF TECHNOLOGY PASADENA, CALIFORNIA August 1, 1968 TECHNICAL REPORT 32-1288 Copyright © 1968 Jet Propulsion Laboratory California Institute of Technology Prepared Under Contract No. NAS 7-1 00 National Aeronautics & Space Administration Acknowledgment The author wishes to thank W. F. Scott and J. J. Wedel for providing the opportunity to work on the pathfinding problem. Stimulating discussions with Dr. C, L. Lawson, Dr. G. Paine, D. Rennels, J. Rohr, E. Suggs, W. Garrison, and C. Carl are acknowledged by the author. P. Sobel provided the computer program used to generate the perspective drawing of contour configurations. In addition, the guidance provided by J. J. Wedel and D. K. Rubin is gratefully acknowledged. JPL TECHNICAL REPORT 32-1288 Hi Page intentionally left blank ^SCEDIRG P AGE BEAEfK HOT fllfflED, Contents I. HIIIUUUVHUII ....... 11. Mathematical Development A. Proposition 1 ...... B. Proposition 2 III. The Pathfinding Algorithm . . A. Main Algorithm ...... B. Right Scan Algorithm ...... C Simulation of Topography . . D. Computer Program for the Pathfin IV. Conclusion .......... References .. ding Algorithm and Results . 2 2 3 4 4 5 5 6 6 20 Figures 1 . Box canyon problem 2. Confour configuration constrvcfed by use of Gaussian hills . . 3. Perspective drawing of contour configuration .. . . ., . . . 4. A maze constructed by use of Gaussian density functions . . . 5. Graph for calculating and constructing any configuration required for the simulation of terrains , 6. Flow chart of computer program, main algorithm , .. . . : . . 7. Flow chart of computer program, left scan algorithm . . . . 8. Flow chart of computer program, right scan algorithm .... 9. A simple obstacle course of five Gaussian hills . , . . . . . 10. A simple box canyon configuration ] 1 . A maze in which the starting point is outside of the maze and the target point is inside . 12. Same maze in which the starting point is inside the maze and the target point is outside . . 13. Result of the robot crawling on and over hills ....... 4 7 8 9 10 11 13 14 15 16 17 18 19 JPL TECHNICAL REPORT 32-I28B Abstract A pathfinding algorithm has been developed for an autonomous myopic roving vehicle. With the assumption that a path exists between two points, two proposi- tions are proved. Proposition 1 is concerned with no obstacles and proposition 2 is concerned with at least one obstacle. Various conditions are established and terms defined. Three algorithms, necessary to direct the robot, are main, left scan, and right scan. The decisions for the navigation, control, and obstacle avoidance of the rover are based mainly on myopic (local) information of the terrain. The use of Gaussian density functions to simulate topography is considered to be novel A FORTRAN IV computer program was written to implement the path- finding algorithm, and the results of the computer-program runs were satisfactory. vi JPL TECHNICAL REPORT 32-1288 A Pathfinding Algorithm for a Myopic Robot I. Introduction It has been more than ten years since E. F. Moore published his article on pathfinding algorithms (Ref. 1). In 1961, C, Y. Lee published his paper on an algorithm for path connections (Ref. 2). The algorithms discussed in the two references have three basic assumptions in common: (I) the map is completely known, (2) each path can be retraced, and (3) an optimum path can be deter- mined. The question arises as to what degree of a priori information about the map must be known in order to determine a path from one point to another point such that it will satisfy a given set of constraints. Here, one may not be interested in obtaining the shortest path, but rather a safe path from one point to another point (i.e., if such a path exists). The impetus for the above question stems from the application of pathfinding algorithms to unmanned planetary exploration, such as the navigation and control of an autonomous roving vehicle on the sur- face of Mars to explore its topography. It is assumed that various orbital reconnaissances, similar to that of the Lunar Orbiter, have been performed and a gross knowl- edge of the topography of the planet is available. Conse- quently, the landing site and the various interesting target areas to be visited can be determined. The transmission of the orbital reconnaissance infor- mation from a distant planet may take many weeks to accomplish because of limited transmitter power. Be- cause of this limitation, if one is to land a roving vehicle on a distant planet, the continuous direct control of the vehicle from earth, as in the case of the Surveyor, will be extremely time-consuming and will probably prove to be infeasible. Consider the case of the Mariner Mars 1964 mission. Each television picture consisted of a 200- X 200-element matrix in which each element con- sisted of six bits. Since the transmission data rate was 8-1/3 bits/s, it took eight hours to assemble one tele- vision picture. Furthermore, direct control from earth of the vehicles' motion on distant planets will be extremely difficult because of transport lag in the control loop (Ref, 3). This makes the use of direct control of the vehicle from earth prohibitive. Therefore, the roving ve- hicle should be autonomous, with minimal command requirements for control of motion from earth. JPL TECHNICAL REPORT 32-1288 1 It is the purpose of this report to discuss the results of a study involving a pathfinding algorithm for an autono- mous roving vehicle. The algorithm requires only infor- mation that is within the field-of-view of die vehicle (i.e., local information). Essentially, the study involves designing a pathfinding algorithm for a myopic robot, the requirements of which are as follows: (1) The robot shall see the terrain that is within its scanning range. (2) Any obstacles within the robot's scanning range may be sensed. (3) The initial starting coordinates (the landing point) shall be given. (4) The target coordinates to be visited shall be given. (5) If a path exists, the algorithm shall find the path. (6) The algorithm shall avoid hazardous obstacles and be able to crawl on and over safe obstacles. (7) The algorithm shall use a minimal number of memory locations for the navigational path. 11. Mathematical Development The pathfinding algorithms developed in this report are based upon two propositions: (1) If a path exists from the point P , (X , Y ), to the point P n , (X», Y»), and there are no obstacles be- tween the two points, then the path connecting these two points can be found, (2) If a path exists from the Point P , (X , Y ), to the point P n , :(X», Y„), and at least one obstacle exists between the two points, then following either the right or left contour of the obstacle and always heading toward the target point P n will result in determining a path between P and P n . The above propositions assume that the obstacles have contour lines and that each obstacle has finite dimension .(le., no infinitely thin obstacles). The proof of the above two propositions is based on whether a target distance sequence contains an element that can be made arbi- trarily small or not. If such an element exists, then the target point is reached. Otherwise, the algorithm, which makes use of the above propositions, will result in limit- cycle oscillation. Definition 1. An acceptable point is defined as a point (X,Y) such that |F(X,Y) j < E, where F(X 3 Y) is a contin- uous function that describes the terrain and E is the elevation limit. Definition 2. A path is defined as a route that connects two points (Xi,Y.i) and (X 7 - 5 Y ; -) such that the elevation of each point of the route is jF(X,Y) | < E. Definition 3. An obstacle is defined as a finite bounded region of a function whose amplitude or values are greater than E, where |F(X,Y)| > E. \ A. Proposition I If there exists a path from the point P , (X 0? Yo), to the i point P w , (X„,Y n ), and there are no obstacles between the points P and P w , then the path can be found by the algorithm. Proof: Let the first intermediate point of travel be (X 1? Yi) such that X x = X + r*cos<9! Yx = Y ■■+ r*smB t where r is a fixed distance increment (scanning range) and 9 1 = tan \X n — Xo/ In general, X i+1 s= Xi + r*cos^ i+1 Y i+1 = Yi 4* r*sin^ i+1 where i+i = tan \ X n *— Xi / Since there are no obstacles between P and P n , then every point on the line P Q P n is an acceptable point and 6i == 6 X for all L Let the target distance sequence be {d u d 2 , ■• • • , d n } 4 = l(X n - X^) 2 + (Y, - Y^TV^ By proper choice of r, the final d% can be made as small as one quantized r (Le., d^ < r). Hence, the tar- get is reached. JPL TECHNICAL REPORT 32-1288 Proposition 1 essentially states that, if the starting point (X ,Y o ) and the target point (X„,Y„) have the prop- erty that |.F(Xo,Yo) | < £ and \F(X ny Y n ) | < E, and there are no obstacles between these two points |F(X,Y)| < E for all (x,y) between these two points, then we ean de- termine a path that connects these points. The idea of proposition 1 is rather obvious. However, the introduc- tion and use of the target distance sequence in proving proposition 1 is the main reason for the detailed proof. Proposition 2 will also make use of the target distance sequence argument. B. Proposition 2 If a path exists from the point P , (X ,Y ), to the point P w , (X„,Y n )> and at least one obstacle exists between the two points, then following either the right or left con- tour of the obstacle and always heading toward the tar- get, P n , will result in determining a path P P n * Proof; This proposition will be proven by the use of mathe- matical induction. It will be shown that the proposi- tion is true for one obstacle between P and P„. If it is assumed to be true for m obstacles, then it can be shown to be true for m 4- 1 obstacles between P and P w . Let the one obstacle between P and P n have the contour represented by F(X,Y), Let the first point of travel from (X ,Y ) to (Xi,Yi) be P 1? such that X x = X + r^cos$ 1 Y t = Y + r*sm$ % where r (the scanning range) is the distance increment, and^^tan-^^-— -) The point (X ,Y ) has a neighborhood that eontaius some acceptable points, because the assumption of a path exists between the points P and P n . Let the acceptable contour elevation limits be given as E. Evaluate F(X 1 ,Y 1 ). If \F(X 1 ,Y 1 )\ < E, then (X l9 Y ± ) is an acceptable point. Now replace (X ,Y ) by (X^Ya), then proceed to evaluate (X;,Yi) for i = 2, 3, • • • , etc. However, if \F(X 1 J 1 ) | > E, replace 6 t by t ±A0. If X + AO is used in determining (X l5 Y x ), the left con- tour is being followed. If 6 X - AO is used, then the right contour is being followed. Evaluate the new F(X 1 ,Y 1 ) by varying AO, until an acceptable point is determined. Also, determine the distance from (X^Yt) to (XnJn) i.e., rf i 2 =(X 7l -X 1 ) 2 + (Y ft -Y 1 ) 2 The angular increment and decrement in AO is 1 deg. The scanning process is continued until a first ac- ceptable point is found. This point also determines whether the right or left contour is to be followed. The crawling process is repeated and a target dis- tance sequence {d x , d 2 , '• ■• • , d%}, is generated until an acceptable point (X ft ,Yfc) such that di > 4 +1 = [(X n - X,) 2 + (Y n - Y*) 2 ] *'* is satisfied. Term d$ was the minimal distance from the target to (X h Yj), the point where the obstacle was first encountered and k > jf. From the point (Xfc,Y fe ) to (X„,Y»), we can apply proposition 1. If the target has not been reached after the use of proposition 1, the above scanning is repeated until the target is reached. Therefore, proposition 2 is true for one obstacle. Assume that proposition 2 is true for m obstacles. We will have to prove that the proposition is also true for m + 1 obstacles. Let the intermediate point of travel from (Xi,Yi) to (Xi+i,Yi+.i) be P i+1 , such that X i+1 == Xi + f*cas0 4+ i Y Ut = Y i + r*sfo0, +1 0$*i == tan~ \ X n — Xi / The expression Xi,Y* is the point where It departed from obstacle m and encountered the m + 1 th obstacle. Term di is the minimal distance from the target to .(Xi,Yi). Let the acceptable contour elevation limit be the same as before, E. Evaluate F(Xi + i,Y i+1 ). If |F(X i+1 ,Y i+1 )| < E, then .(Xi +1 ,Y i+1 ) is an acceptable point. Now replace (X h Yi) by (X i+1 ,Yi + i). Then, pro- ceed to evaluate (Xi +2 ,Yi +2 ), etc. However, if |F(X i+1 ,Y i+1 )| > E> replace $ Ul by $ M dr AO. Eval- uate the new |F{Xi +1 ,Y i+1 )| until an acceptable point is determined. Also, determine whether d i+1 < di, i.e., (X w -X i+1 ) 2 + (Y w -Y u *) 2 < (Xn-XO 2 + {Yn-Ytf JPL TECHNICAL REPORT 32-1288 If after some P iterations, d p < di, and there are no obstacles between P v and P n , we can apply propo- sition 1. In general, there is a monotonic decreasing subsequence of {di,<2 2? * • \d n % say {dmud^z,* • • A«} 5 where each dm% is a local miirtaum distance to the target such that dmi +1 < dmi for all i. Hence, the tar- get is reached. Therefore, proposition 2 is true for m + 1 obstacles. The proof of proposition 2 can be simplified by use of inductive argument on each obstacle grossly, ratitier than point by point. Any obstacles that merge together can be considered as a single obstacle. The value of the target distance sequence element controls the use of either proposition 1 or proposition 2. Consider the case of a box canyon. Let <i& be the distance from the end of the box canyon (Fig. 1) to the target. Assume that the right contour is being followed. Then all target distance sequence elements <4+i> dh+ 2 , •*•, generated will be greater than d k . Thus, the right contour is being followed until a dm < djc is found and proposition 1 is applied. Then, <4 is replaced by d^. This iteration process is con- tinued until the target is reached. d . = d v , < d. = d. mm 1] 1 k Fig. 1. Box canyon problem Hi. The Pathfinding Algorithm The pathfinding algorithm consists of three algorithms, which are called main algorithm, left scan algorithm, and right scan algorithm. The main algorithm directs the robot to move either straight ahead, in the right direc- tion, or in the left direction. The left scan algorithm directs the robot to move in the left direction only. The right scan algorithm can only direct the robot to go to the right. The right and left scan algorithms enable the robot to navigate out of box canyons. A. Main Algorithm The main algorithm can be described by the following steps: (1) Construct a vector, called target vector, by using the starting point (X ,Y ) and the target point (2) Determine the azimuth of the target vector and call it 8. (3) Let the next point of travel be (x,y) such that x = X + r*cos& ^ y == Y 4- r*sin# where r is the maximum scanning range of the robot and is defined the same as step (2). (4) Evaluate the contour map F(x,y) at the next point of travel (x,y). If \F(x,y) \ is within a prescribed contour limit, i.e., J F(x,y) | < E is defined as the elevation limit (Definition 1), go to step (6); if not, goto step (5). (5) Start scanning by varying the azimuth in incre- ments of 1 deg (i.e., ± 1 deg) until an acceptable contour limit is reached. The scanning process scans 1 deg to the left of the azimuth, then 1 deg to the right; 2 deg to the left, then 2 deg to the right, etc. If at (x,y), F(x,y) has an acceptable con- tour limit, go to step (6). If no such point exists, go to step (8). (6) Determine whether the target has been reached or not. If the target has not been reached, replace (X 6 ,Y&) with (Xo,Yo), where (X 6 ,Y&) is the previous point. Also replace (X 03 Y ) with (x 9 y). If x = X + r^cos^ y = Y + r*sin^ is an acceptable point, set the right counter, CTR = 0.0, and the left counter CTL == 0.0. If the point x = X + r*cos (0 + AO) y = Y + r*sin (6 + AS) is an acceptable point, set CTR = 1.0 and compute JPL TECHNICAL REPORT 32-1288 If the point x = X + r*cos(0 ~ AS) ^ = Y G + r*sin($ - A0) is an acceptable point, set CTL = 1.0 and compute ZV= l(x t - x)* + (y t - y)*V /2 Go to step (7). If the target has been reached, the job is finished. If both right and left counters are not 1.0, go to step (I). (7) If both counters are 1.0, the robot is trapped. If the distance from the right point to the target is shorter than the distance of the left point to the target, go to the right scan algorithm. Otherwise, go to the left scan algorithm. (8) The robot is trapped. In this case, there exists no path from point F to P t . Hence, there exist no ac- ceptable points in the neighborhood of P Q . The robot may have landed on the peak of a mountain. B. Right Scan Algorithm Because the left scan algorithm is similar to the right scan algorithm, it is sufficient to describe the right scan algorithm. In order to force the algorithm to crawl along the contour edge, a crawling vector is defined. The right scan algorithm can be described by the following steps: (1) Construct a target vector using (X ,Y ) and (X tj Y t ), Also construct a crawling vector using (X&,Y&) and (X ,Y ). The minimal distance from (x 9 y) to (X t ,Y t ) at the time of encountering the obstacle is Dmin = D t . (2) Determine the azimuth of both the target vector and the crawling vector. Call the crawling vec- tor azimuth 01. (3) Let the next point of travel be (x,y) such that x = X + r*cos(0l + 90°) y = Y + r*sin(0l 4- 90°) where r is the maximum scanning range and 01 is defined the same as step (2). (4) Evaluate the contour map F(x,y) at (x,y). If |F(x,t/)| at {x,y) is within the prescribed contour limit, go to step (6); if not, decrement 01 by one angular degree until an acceptable contour value of F(x,y) is obtained, The maximum decrement is 270 deg. Once an acceptable (x,y) has been ob- tained, go to step (5). (5) Determine the distance from (X,Y) to (Xt,Y t ) and call it Dt. Replace <X 6 ,Y 6 ) with (X 0) Y ); and, (X ,Y ) with {x y y). Then go to step (6). (6) If Dmin < D t , go back to step (1). However, if Dmin > Dt, go to step (7). (7) Evaluate F(x,y). If | F(x,y)\ > E, go back to step (1). However, if | F{x,y) \ < E, reset the left and right counter to zero and return to the main algorithm. The point (x,y) is x — X 4- r*cos0 y = Y + r*sin0. C. Simulation of Topography In the course of developing an algorithm for the myopic robot, the problem encountered of inputting data to the algorithm (for computer simulation) was difficult because the data had to meet requirement (2) stated in Section I. Since the input data was to be topography, the data should have various levels of contours. A novel solution for simulation of terrain was made by using Gaussian density functions. Using the Gaussian density- functions, one can simulate almost all terrain simply by summing a series of "Gaussian hills." The locations of these Gaussian hills can be fixed by assigning the means, /ia, and /%, the desired coordinates. The shapes of the Gaussian hills can be controlled by varying the value of the standard deviations, <j x and o y . The height of the Gaussian hills can be varied by using an appropriate con- stant (positive and negative) multiplier of the Gaussian density function. Since the use of a set of Gaussian hills to simulate topography will result in a very smooth surface, the approximated terrain will not represent an exact topog- raphy. However, this technique is so simple to use, all terrain considered in this report is made of Gaussian hills. The Gaussian hill technique can also be used to classify and sense obstacles by covering each obstacle with a Gaussian hill. Figure 2 shows a contour config- uration that can be constructed by using Gaussian hills. Figure 3 is a perspective drawing of the contour config- uration of Fig. 2. Figure 4 shows a maze constructed by use of Gaussian density functions. Figure 5 enables one to calculate and construct any configuration required for the simulation of topography. JPL TECHNICAL REPORT 32-1288 D. Computer Program for the Pathfinding Algorithm and Results A computer program was coded in FORTRAN IV language as implemented in the IBM 7090/94 IBJOB System. The flow charts for the pathfinding algorithms are shown in Figs. 6-8. The computer program, which plots the contour lines of the obstacle, was developed by Dr. Charles L. Lawson (Ref. 4) of the Computation and Analysis Section at Jet Propulsion Laboratory. The pathfinding computer program was organized so that the contour lines of the obstacle were plotted first, and then the path from the starting point to the target was plotted. Various configurations of obstacle courses were made and the robot satisfactorily navigated through each course. Figure 9 shows a simple obstacle course of five Gaussian hills. The path, which connects the starting and target points, satisfies the contour elevation con- straint of E == I (i.e., |F(x,t/)| < 1.0), The scanning range r is set at 0,1 unit. This means that the robot will see no further than 0.1 unit ahead. Figure 10 shows a simple "box canyon" configuration. In this case, there are two paths to the target point. The path determined by the algorithm is certainly not the shortest path. The shortest path was not chosen, because the decision to go to the right scan program was based on the minimum azimuth scanning angle to the right. Also, the distance from the right scanned point to the target point was shorter than the distance to the left scanned point. Using local information only, there are no methods by which one can determine the shortest path between two points. Figure 11 shows a maze in which the starting point is outside of the maze and the target point is inside of the maze. Figure 12 shows the same maze as Fig. 11; how- ever, the starting point is inside the maze and the target point is outside of the maze. In all cases which were run on the computer, paths were found for each case, IV. Conclusion This report has demonstrated that it is possible to find * a path connecting two points on a continuous contour map, using only local information. The algorithm used to find a path is based on two propositions. In turn, these ^ propositions were based on intuitive ideas that are used in unknown areas. One of the assumptions used in prov- ing the propositions was that there exists at least one path from the starting point to the target point. This is not an unreasonable assumption. If one were to land a spacecraft inside a crater and the wall of the crater was very steep, such that the vehicle could not extricate itself from the crater, one would have to terminate the mission. The algorithm developed in this report might be im- proved by incorporating certain local terrain informa- tion, such as the hidden lines of obstacles (Ref. 5). The slopes of local areas can also be incorporated so that the vehicle will have minimal tilt angles while it travels from one point to another point. Furthermore, if we de- fine a subpath as \f(%i$i) — /(£*-i,J/»-i).] < £ for all I's and for a distance of r, then the algorithm will allow the robot to crawl on and over hills. Figure 13 shows the result of the robot crawling on and over hills. The present scanning portion of the computer program is based on simple strategy. Future work will incorporate the scanning strategy of ranging radar. JPL TECHNICAL REPORT 32rl28B 3,oaa * ■* illlilli : $4$.&, Fig. 2. Contour configuration constructed by use of Gaussian hills JPL TECHNICAL REPORT 32-1288 Fig. 3. Perspective drawing of contour configuration JPL TECHNICAL REPORT 32-1288 s.aoai «m$ *$.i$M. ■■ *4. t *m. : ■*»:*>#»■ . .-$..» . ^ -!,s*»; ! $01 I « -\*80 *.C Fig. 4. A maze constructed by use of Gaussian density functions JPL TECHNICAL REPORT 32-1288 i<r 10 10 / A / ^2 *(x) = -{Ax/a- ) Ax k ~ cr \ \ ,o" 3 0.4 0.8 1.2 1.6 2.0 2.4 2.8 k Fig. 5. Graph for calculating and constructing any configuration required for the simulation of terrains 10 JPL TECHNICAL REPORT 32-1288 r^ en < w I— o o 6 > ^ UJ t- Q o > o£ _ X ». on , t— — li l/> X uj co 1— T LO 2uT . O 1— z S <£u o_ o IS o OZ!5 C!) Z ANNIN EVATIO OSURE *^ < V _J r-J CO L1J D LO H- CM ^ CM O > i— ^>^ UJ H- 3 + CM o O X 1— X 11 z ^ Q CD oo o U m * h- oc a. + ^ o o X u 11 X JtooouE mum f JPL TECHNICAL REPORT 32-7288 o . o U t— O QZ h- t— aa 7 1— < ) Z H- u O 1— U- LJJ i an I— J— LU LU co CO U X > < __j o o CL, LU X > ^-s cd q> < < a> <d LU " >— - 1— CL. -co _ o z £ U co * * o C£ ££ u + + o o X >- 11 If X > ■Q LU CO 1— LU CO _l o — 1 o <J T I £ S cm >- 1 2<^ LU \ VI \ _i Q ^ a> CD < < + + CD CD LU >— ' *»— " .f— CO CL. o z 2 CO * o D£ Ctl u + + o o X > ii 1! X >- VI co >i £ < Q£ LU O ■m o Q - ol pp *- z zl o< >< CO tz LU ££ ^ a f(p«>OT JEfflffl o o JP c "5 E £ o I a. D a. E o u **- O t 11 Page intentionally left blank PRECEDING PAGE BLAHK not w&Sb. f LEFT SCAN "\ V ^ PROGRAM J COMPUTE CRAWLING VECTOR Q\ AND 9 6} = TAN" •1 f Y b~ Y V X 8= TAN -1 , Y T- Y x T -x c COMPUTE x = X G + R*COS (01 + 9.0 -A3) y = Y + R*S|N (01 + 9O-A0) NO COMPUTE D t=V( x t- x f + f y t- y V SET AG = A0 + 1° YES REPLACE DMIN BY D, REPLACE x b 8YX ANDX BY x Y b BY Y Q AND Y Q BYy NO NO Fig. 7. Flow chart of computer program, left scan algorithm JPL TECHNICAL REPORT 32-1288 13 RIGHT SCAN PROGRAM REPLACE: DM IN BY D COMPUTE CRAWLING VECTOR 01 AND 01 = TAN = TAN ■lf Y b" Y X b~ X \V X 0J COMPUTE x = X + R*COS (01 - 90 +A0) y == Y +R*SIN (01 -90+ AG) YES NO i SET A.6 = AS +1° COMPUTE 3 t = V( x t" x ) 2 + ( y t" yX2 T REPLACE X b by X Q AND X Q BY x Y L BYY^AND Y n BY y b ' YES NO YES £ NO Fig. 8. Flow chart of computer program, right scan algorithm 14 JPL TECHNICAL REPORT 32-1288 ;!.*«■■ ''■ ■;.':*v0Oij ' ' . :t,*Hfl» Fig. 9. A simple obstacle course of five Gaussian hills JPL TECHNICAL REPORT 32-1288 15 5,000 Fig. 10. A simple box canyon configuration 16 JPL TECHNICAL REPORT 32-1288 4.0^0 f~.. 5,000 i.. a.aoo 4*.., t.oaa 4>- -1*00© *-.. -ff.0O8 #~ -9,000' *■■ STARTING ~4,&m &■ . POINT -5.000 V ELEVATION IN UNITS D = 1 E = 3 F = 5 ~9.OO0 -4. DOS -3*000 ■ -2.000 ' -1*000 0.000 1*000 ■ * , POO 3,000 &.0O0 ■S.OOO X Fig. 11.. A maze in which the starting point is outside of the maze and the target point is inside JPL TECHNICAL REPORT 32-1288 17 ■'.4;*.!Wtti 3.CI0® ^ :$>: : £» Fig. 1 2. Same maze in which the starting point is inside the maze and the target point is outside 18 JPL TECHNICAL REPORT 32-1288 MMP .'•'■ 3 » OHO : , i **••*■•'-■•. •...;.;...■.., ■ . .. : ■ilttt iiUlK ;■:>■;■''*" ' ^^^^^^^^^^fcpppMfiPiss •'. ;-..*. ;;pJW>- : ^'v r .i^ r: ^^'..-..'..f:'.i.-..>»-v^ ■.,.-,. ..■,!.. ,.;..., STARTING POINT j . : :; '<*:*" v d;c*py ;^ : ix ••••• ■■'■ '■ ? : ; ^•■;- ; t- : ;^:; | ||||||j| iHlltl llllll Willi lllill ^ 5 '' D I I , III F ^ 5 II two . X I ^.i,-ii.*.-:>>v.- * : ;^Vi^l'^v:' : ^';: ; :vS : v| Fig. 13. Result of the robot crawling on and over hills JPL TECHNICAL REPORT 32-1288 19 References 1. Moore, E, F., "Shortest Path through a Maze," Annals of the Computation Laboratory of Harvard University, Vol. 30, pp. 285-292, Harvard University Press, Cambridge, Mass., 1959. 2. Lee, C. Y., "An Algorithm for Path Connections and Its Applications/' IEEE Trans. Electron. Compute pp. 346-365, Sept. 1961. 3. Miller, B. P., et al., Roving Vehicle Motion Control, Final Report TR 67-60. AC Electronics, Defense Research Laboratories, Santa Barbara, Calif., Dec. 1967. 4. Lawson, C. L. ? Block, N., and Garrett, R. S., "Computer Subroutine for Con- tour Plotting," in Supporting Research and Advanced Development, Space Programs Summary 37-32, Vol. IV, p. 18. Jet Propulsion Laboratory, Pasadena, Calif., Feb. 1-Mar. 31, 1965. 5. Freeman, H., and Loutrel, P. P., "An Algorithm for the Solution of the Two- Dimensional 'Hidden-Line' Problem," IEEE Trans. Electron. Compute Vol. EC-16, No. 6, pp. 784.-790, Dec. 1967. 20 JPL TECHNICAL REPORT 32-1288